package com.c2b.algorithm.leetcode.hot100;

/**
 * <a href="https://leetcode.cn/problems/implement-trie-prefix-tree/description/">实现 Trie (前缀树)</a>
 *
 * @author c2b
 * @since 2023/4/20 16:32
 */
public class Hot208Trie {

    /**
     * <p>
     * Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
     * <p>
     * 请你实现 Trie 类：
     * <li>Trie() 初始化前缀树对象。</li>
     * <li>void insert(String word) 向前缀树中插入字符串 word 。</li>
     * <li>boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。</li>
     * <li>boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。</li>
     * <p>示例：</p>
     * <pre>
     * 输入
     *      ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
     *      [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
     * 输出
     *      [null, null, true, false, true, null, true]
     *
     * 解释
     *      Trie trie = new Trie();
     *      trie.insert("apple");
     *      trie.search("apple");   // 返回 True
     *      trie.search("app");     // 返回 False
     *      trie.startsWith("app"); // 返回 True
     *      trie.insert("app");
     *      trie.search("app");     // 返回 True
     * </pre>
     * <b>提示：</b>
     * <pre>1 <= word.length, prefix.length <= 2000</pre>
     * <pre>word 和 prefix 仅由小写英文字母组成</pre>
     * <pre>insert、search 和 startsWith 调用次数 总计 不超过 3 * 10^4 次</pre>
     */
    static class Trie {
        private final Trie[] children;
        private boolean isEnd;

        public Trie() {
            this.children = new Trie[26];
            this.isEnd = false;
        }

        /**
         * 插入字符串。
         * <p>
         * 我们从字典树的根开始，插入字符串。对于当前字符对应的子节点，有两种情况：
         * <li>子节点存在。沿着指针移动到子节点，继续处理下一个字符。</li>
         * <li>子节点不存在。创建一个新的子节点，记录在 children 数组的对应位置上，然后沿着指针移动到子节点，继续搜索下一个字符。</li>
         * ==》重复以上步骤，直到处理字符串的最后一个字符，然后将当前节点标记为字符串的结尾。
         * </p>
         *
         * @param word 要插入的字符串
         */
        public void insert(String word) {
            Trie currTrie = this;
            // 在当前树的index位置查找子树是否存在，不存在就创建。存在进入下一个字符
            for (int i = 0; i < word.length(); i++) {
                int index = word.charAt(i) - 'a';
                Trie childTrie = currTrie.children[index];
                if (childTrie == null) {
                    currTrie.children[index] = new Trie();
                }
                // 让子树成为当前树
                currTrie = currTrie.children[index];
            }
            // 找到最后一层，让isEnd变为true
            currTrie.isEnd = true;
        }

        /**
         * 查找字符串。
         * <p>
         * 我们从字典树的根开始，查找字符串。对于当前字符对应的子节点，有两种情况：
         * <li>子节点存在。沿着指针移动到子节点，继续搜索下一个字符。</li>
         * <li>子节点不存在。说明字典树中不包含该字符串，返回null。</li>
         * ==》重复以上步骤，直到返回null或搜索完字符串的最后一个字符。<br>
         * 若搜索到了字符串的末尾，就说明字典树中存在以改字符串为前缀的字符串。判断isEnd是否为true,若为true则说明字典树中存在该字符串
         * </p>
         *
         * @param word 要查找的字符串
         * @return 存在则为tru，不存在则为false
         */
        public boolean search(String word) {
            Trie currTire = this;
            for (int i = 0; i < word.length(); i++) {
                int index = word.charAt(i) - 'a';
                if (currTire.children[index] == null) {
                    return false;
                }
                // 进入子树
                currTire = currTire.children[index];
            }
            return currTire.isEnd;
        }

        /**
         * 查找前缀。
         * <p>
         * 我们从字典树的根开始，查找前缀。对于当前字符对应的子节点，有两种情况：
         * <li>子节点存在。沿着指针移动到子节点，继续搜索下一个字符。</li>
         * <li>子节点不存在。说明字典树中不包含该前缀，返回null。</li>
         * ==》重复以上步骤，直到返回null或搜索完前缀的最后一个字符。<br>
         * 若搜索到了前缀的末尾，就说明字典树中存在该前缀。
         * </p>
         *
         * @param prefix 要查找的字符串前缀
         * @return 存在则为tru，不存在则为false
         */
        public boolean startsWith(String prefix) {
            Trie currTire = this;
            for (int i = 0; i < prefix.length(); i++) {
                int index = prefix.charAt(i) - 'a';
                if (currTire.children[index] == null) {
                    return false;
                }
                currTire = currTire.children[index];
            }
            return true;
        }
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));   // 返回 True
        System.out.println(trie.search("app"));     // 返回 False
        System.out.println(trie.startsWith("app")); // 返回 True
        trie.insert("app");
        System.out.println(trie.search("app"));     // 返回 True

    }


}
